package LeetCode;

import com.company.Tree.Tree;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}23:33
 */
public class M2 {//重建二叉树
    public static void main(String[] args) {
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        M2 m2 = new M2();
        TreeNode node = m2.buildTree(preorder,inorder);
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public TreeNode buildTree(int[] preorder,int[] inorder){
        if (preorder==null||preorder.length==0||inorder==null||inorder.length==0){
            return null;
        }
        return help(preorder,0,preorder.length-1,inorder,0,inorder.length-10);
    }

    public TreeNode help(int[] preorder,int pStart,int pEnde,int[] inorder,int iStart,int iEnd){
        if (pStart > pEnde || iStart > iEnd){
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[pStart]);//前序就是头节点

        //在中序中找到头节点
        int index = 0;
        while (inorder[iStart+index] == preorder[pStart]){//找到  相位差
            index++;
        }

        treeNode.left = help(preorder,pStart+1,pStart+index,inorder,iStart,iStart+index-1);
        treeNode.right = help(preorder,pStart+index+1,pEnde,inorder,iStart+index+1,iEnd);
        return treeNode;
    }

//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        if (preorder==null||preorder.length==0||inorder==null||inorder.length==0){//规范程序鲁棒性
//            return null;
//        }
//        return help(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
//    }
//
//    public TreeNode help(int[] preorder,int pStart,int pEnd,int[] inorder,int iStart,int iEnd){
//        if (pStart > pEnd || iStart > iEnd){
//            return null;
//        }
//
//        TreeNode node = new TreeNode(preorder[pStart]);//创建第一个父节点
//
//        int index = 0;
//        while (inorder[iStart + index] != preorder[pStart]){//找到父节点
//            index++;
//        }
//
//        //重建左子树
//        node.left = help(preorder,pStart+1,pStart+index,inorder,iStart,iStart+index-1);
//        node.right = help(preorder,pStart+index+1,pEnd,inorder,iStart+index+1,iEnd);
//        return node;
//    }
}
